class Solution {
public:
    int pre[90000]={0};
    int find(int x){
        if(pre[x]==x) return x;
        else
        return pre[x]=find(pre[x]);
     }
     void join(int x,int y){
        if(find(x)!=find(y)){
            pre[find(x)]=find(y);
        }
     }
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        set<int> sum;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='1'){
                    pre[i * m + j] = i * m + j;
                    if(i>0 && grid[i-1][j]=='1' ){
                        join((i-1) * m + j,i * m + j);
                    }
                    if(j>0 && grid[i][j-1]=='1'){
                        join(i * m + j,i * m + j-1);
                    }
                }
                else{
                    pre[i * m + j] = -1;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='1'){
                    sum.insert(find(i * m + j));
                }
            }
        }
        return sum.size();
    }
};
